package bill.java.interview.salesforce;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

/***
 * 
 * 
 * 
 * 
 * /** Add/remove programs. each program may be dependent on a set of programs.
 * There are 5 commands: DEPEND p1 p2 p3: P1 depends on p2 and p3 INSTALL p1:
 * install p1 if it has not been installed, install all its dependent programs
 * implicitly. REMOVE p1: remove p1 only if no other programs are dependent on
 * it. Also remove its dependent programs if they can be removed. LIST: list all
 * programs that are installed. END: end the processing? //don't remember.
 * sorry, here is the input data: String[] lines =
 * {" DEPEND  BROWSER HTML   TCPIP  NETGEAR", "DEPEND FTP NETGEAR",
 * "DEPEND TELNET TCPIP NETGEAR", "INSTALL  TCPIP", "INSTALL FTP",
 * "INSTALL BROWSER", "INSTALL foo", "REMOVE TCPIP", "REMOVE NETGEAR",
 * "REMOVE BROWSER", "REMOVE foo", "LIST", "END"};
 * 
 * @author yangliu
 * 
 */
public class ProgramManager {

	private Map<String, Set<String>> dependMap = new HashMap<String, Set<String>>();
	private Map<String, Set<String>> supportMap = new HashMap<String, Set<String>>();
	private Set<String> installedPrograms = new TreeSet<String>();

	
	private void printInternal(){
		System.out.println("*******************************************************");
		System.out.println("dependent Map: " + dependMap);
		System.out.println("supportMap Map: " + supportMap);
		System.out.println("installedPrograms: " + installedPrograms);
	}
	public static void main(String args[]) {
		// read the command line by line
		  
        
		String[] lines = { "DEPEND  BROWSER HTML   TCPIP  NETGEAR",
				"DEPEND FTP NETGEAR", "DEPEND TELNET TCPIP NETGEAR",
				"INSTALL  TCPIP", "INSTALL FTP", "INSTALL BROWSER",
				"INSTALL foo", "REMOVE TCPIP", "REMOVE NETGEAR",
				"REMOVE BROWSER", "REMOVE foo", "LIST", "END" };
		ProgramManager programMan = new ProgramManager();
		for (String line : lines) {
			if (line != null && !line.trim().isEmpty()) {

				// build a command
				Command command = buildCommand(line);
				CommandName commandName = command.getCommandName();
				switch (commandName) {
				case DEPEND:
					programMan.addDependency(command);
					programMan.printInternal();
					break;
				case INSTALL:
					programMan.install(command);
					programMan.printInternal();
					break;
				case REMOVE:
					programMan.remove(command);
					programMan.printInternal();
					break;
				case LIST:
					programMan.list();
					programMan.printInternal();
					break;
				case END:
					programMan.printInternal();
					programMan.addDependency(command);
					break;
				default:

				}

			}
		}

	}

	private static Command buildCommand(String line) {

		Command result = null;
		StringTokenizer st = new StringTokenizer(line);
		String command = st.nextToken();
		if ("DEPEND".equalsIgnoreCase(command)) {
			result = new Command(CommandName.DEPEND);
		}
		// case 2 for install
		else if ("INSTALL".equalsIgnoreCase(command)) {
			result = new Command(CommandName.INSTALL);
		}
		// case 3 for remove
		else if ("REMOVE".equalsIgnoreCase(command)) {
			result = new Command(CommandName.REMOVE);
		} else if ("LIST".equalsIgnoreCase(command)) {
			result = new Command(CommandName.LIST);
		} else if ("END".equalsIgnoreCase(command)) {
			result = new Command(CommandName.END);
		} else {
			result = Command.UNKNOWN_COMMAND;
		}

		if (result != Command.UNKNOWN_COMMAND) {
			List<String> options = new ArrayList<String>();
			while (st.hasMoreTokens()) {
				options.add(st.nextToken());
			}
			result.setOptions(options);
		}

		return result;
	}

	private static class Program {
		private String name;

		private Program(String name) {
			this.name = name;
		}
	}

	private static enum CommandName {
		DEPEND, INSTALL, REMOVE, LIST, END;
	}

	private static class Command {
		private CommandName commandName;

		public CommandName getCommandName() {
			return commandName;
		}

		public void setCommandName(CommandName commandName) {
			this.commandName = commandName;
		}

		public List<String> getOptions() {
			return options;
		}

		public void setOptions(List<String> options) {
			this.options = options;
		}

		private List<String> options;

		public Command(CommandName name) {
			this.commandName = name;
		}

		public static Command UNKNOWN_COMMAND = new Command(null);

	}

	public void addDependency(Command dependCom) {

		List<String> options = dependCom.getOptions();
		Iterator<String> iterator = options.iterator();

		/**
		 * 1. populate or update the dependMap
		 */
		// get the first which is the dependee
		String dependee = null;
		if (iterator.hasNext()) {
			dependee = iterator.next();
		} else {// a depend command without a options. do nothing
			return;
		}

		// retrieve the dependents set
		Set<String> dependents = this.dependMap.get(dependee);

		// the set is not there, create it and put it into the map
		if (dependents == null) {
			dependents = new HashSet<String>();
			this.dependMap.put(dependee, dependents);
		}

		// update the contents of the dependents
		while (iterator.hasNext()) {
			dependents.add(iterator.next());
		}

		/**
		 * 2. populate or update the supportMap
		 */
		for (String dependent : dependents) {
			Set<String> supported = this.supportMap.get(dependent);
			if (supported == null) {
				supported = new HashSet<String>();
				this.supportMap.put(dependent, supported);
			}
			supported.add(dependee);
		}
	}

	private void install(String program) {
		if (this.installedPrograms.contains(program)) {
			return;
		} else {
			this.installedPrograms.add(program);
			Set<String> dependents = this.dependMap.get(program);
			if (dependents == null || dependents.size() == 0) {
				this.installedPrograms.add(program);
				return;
			} else {
				for (String dependent : dependents) {
					install(dependent);
				}
			}
		}
	}

	public void install(Command installCommand) {
		List<String> options = installCommand.getOptions();
		if (options == null || options.size() != 1) {
			// invalid command
			return;
		}

		String program = options.get(0);
		install(program);
	}

	private void remove(String program) {
		if (!this.installedPrograms.contains(program)) {
			// the program is not installed at all
			return;
		} else {
			Set<String> programs = this.supportMap.get(program);
			if (programs == null || programs.size() == 0) {
				// no other program depends on this program, that is, this
				// program does not support any other program, remove it
				this.installedPrograms.remove(program);
				//update the supportMap and dependMap
				// get rid of the program from all the sets in supported map
				for(Map.Entry<String, Set<String>> entry: this.supportMap.entrySet()){
					Set<String> values = entry.getValue();
					Iterator<String> iterator = values.iterator();
					while(iterator.hasNext()){
						if(program.equals(iterator.next())){
							iterator.remove();
						}
					}
					
				}
				
				
				// get all his dependent programs
				Set<String> dependents = this.dependMap.get(program);
				if (dependents == null || dependents.size() == 0) {
					return;
				} else {
					for (String dependent : dependents) {
						if (dependent != null) {
							remove(dependent);
						}
					}
				}
			} else {// this program supports other program, can not be removed.
				return;
			}
		}
	}

	public void remove(Command removeCommand) {

		List<String> options = removeCommand.getOptions();
		if (options == null || options.size() != 1) {
			// invalid command
			return;
		}

		String program = options.get(0);
		remove(program);
	}

	public void list() {
		for (String installed : this.installedPrograms) {
			System.out.println(installed);
		}

	}

}
